package com.zh.lex;

import java.util.*;
import java.util.concurrent.ConcurrentLinkedQueue;

public class NFA2DFA {

    private final TreeMap<Long, Set<Integer>> nfaStatTable;
    private final TreeMap<Long, Integer> dfaStatTable;
    private final Map<Integer, String> int2strMap;
    private Map<String, Integer> str2intMap;
    private final Integer nfaStartStat;
    private final Set<Integer> nfaEndStat;
    private C startC;

    /**
     * 状态集转 Integer
     */
    private Map<C, Integer> statMap;
    /**
     * statMap 的转置
     */
    private Map<Integer, C> statMapTranspose;

    public NFA2DFA(RE2NFA nfa) {
        nfaStatTable = nfa.getStatJump();
        nfaStartStat = nfa.getStartStat();
        nfaEndStat = nfa.getEndStat();
        str2intMap = new HashMap<>(nfa.getMap().size() << 1);
        int2strMap = new HashMap<>(str2intMap.size() << 1);
        nfa.getMap().forEach((k, v) -> {
            if (null != k && k.startsWith("\\") && k.length() > 1 && !"\\o".equals(k)) {
                k = k.substring(1);
            }
            str2intMap.put(k, v);
            int2strMap.put(v, k);
        });

        statMap = new HashMap<>(nfaStatTable.size() << 1);
        statMapTranspose = new HashMap<>(nfaStatTable.size() << 1);
        dfaStatTable = new TreeMap<>();

    }


    public void displayGraphviz() {
        System.out.println("digraph G {");
        dfaStatTable.forEach((k, v) -> {
            C nc = statMapTranspose.get(v);
            if (nc.isEnd) {
                System.out.println("\"" + nc.toString() + "\" [shape=doublecircle]");
            }
            String re = RE2NFA.displayStr(int2strMap.get(RE2NFA.long2Re(k)));
            C tc = statMapTranspose.get(RE2NFA.long2Stat(k));
            System.out.println("\"" + tc.toString() + "\" -> \"" + nc.toString() + "\" [label=\"" + re + "\"]" );
        });
        System.out.println("}");

    }

    private TreeMap<Long, Set<Integer>> nfaStat1 = new TreeMap<>();

    public NFA2DFA handle() {
    	
        for (Map.Entry<Long, Set<Integer>> e : nfaStatTable.entrySet()) {
            Long k = e.getKey();
            int re = RE2NFA.long2Re(k);
            int stat = RE2NFA.long2Stat(k);
            nfaStat1.put(RE2NFA.int2long(re ,stat), e.getValue());
        }
        {
	    	Set<Integer> si = new HashSet<>();
	    	si.add(nfaStartStat);
	    	startC = new C(si);
	    	statMapTranspose.put(0, startC);
	        statMap.put(startC, 0);
	        handleC(startC);
    	}
        while (queue.size() > 0) {
            C c = queue.poll();
            handleC(c);
        }
        return this;
    }

    private void handleC(C c) {
    	int thisStat = statMap.get(c);
    	Set<Integer> si = c.si;
    	Set<Integer> res = new HashSet<>();
    	for (Integer i : si) {
    		for (long l : nfaStat1.subMap(RE2NFA.int2long(0, i), RE2NFA.int2long(0, i + 1)).keySet()) {
    			int re = RE2NFA.long2Stat(l);
    			if (res.contains(re))
    				continue;
    			res.add(re);
    			int nextStat = getNfaStat(si, re);
                dfaStatTable.put(RE2NFA.int2long(thisStat, re), nextStat);
    		}
    	}
    }
    
    private Queue<C> queue = new ConcurrentLinkedQueue<>();

    /**
     * 返回对应的stat
     * @param s
     * @param re
     * @return
     */
    private int getNfaStat(Set<Integer> s, int re) {
        Set<Integer> si = new HashSet<>();
        for (Integer i : s) {
            Long k = RE2NFA.int2long(i, re);
            Set<Integer> ss = nfaStatTable.get(k);
            if (null != ss && ss.size() > 0)
                si.addAll(ss);
        }
        C c = new C(si);
        if (!statMap.containsKey(c)) {
            statMapTranspose.put(statMap.size() + 2, c);
            statMap.put(c, statMap.size() + 2);
            queue.add(c);
        }
        return statMap.get(c);
    }

    private Map<Integer, String> typeMap;

    void setTypeMap(Map<Integer, String> m) {
        this.typeMap = m;
    }

    public String getType(char[] cs, Token t) {
        if (null == typeMap)
            throw new IllegalArgumentException();

        C c = _getType(cs, t.getStartIndex(), statMap.get(startC), t);
        if (null == c) {
            Character cc;
            if (t.getStartIndex() == t.getEndIndex() && ((cc = cs[t.getStartIndex()]) == ' ' || cc == '\n')) {
                while ((cc = cs[t.getStartIndex()]) == ' ' || cc == '\n') {
                    t.setStartIndex(t.getStartIndex() + 1);
                    if (cc == '\n')
                        t.setLine(t.getLine() + 1);
                    if (t.getStartIndex() == cs.length) {
                        t.setStartIndex(cs.length - 1);
                        t.setEndIndex(cs.length - 1);
                        return null;
                    }
                }
                c = _getType(cs, t.getStartIndex(), statMap.get(startC), t);
            }
        }
        if (null == c) {
            if (t.getEndIndex() == cs.length)
                return null;
            Character ch;
            if ((ch = cs[t.getEndIndex()]) != ' ' && ch != '\n') {
                while ((ch = cs[t.getEndIndex()]) != ' ' && ch != '\n') {
                    t.setEndIndex(t.getEndIndex() + 1);
                    if (ch == '\n')
                        t.setLine(t.getLine() + 1);
                    if (t.getEndIndex() == cs.length) {
                        t.setEndIndex(cs.length - 1);
                        return null;
                    }
                }
            }
            return null;
        }

        return c.type;
    }

    private C _getType(char[] cs, int index, Integer thisStat, Token t) {

        if (cs.length <= index) {
            C tc = statMapTranspose.get(thisStat);
            if (tc.isEnd)
                return tc;
            return null;
        }
        t.setEndIndex(index);
        char c = cs[index];
        if (c == '\n')
            t.setLine(t.getLine() + 1);
        Integer re = str2intMap.get("" + c);
        if (null == re)
            re = str2intMap.get("\\o");
        if (null == re) {
            return null;
        }
        Integer nextC = dfaStatTable.get(RE2NFA.int2long(thisStat, re));
        if (null == nextC)
            return null;
        index++;
        C tc = _getType(cs, index, nextC, t);
        if (null == tc && t.getEndIndex() == index) {
            if (cs.length == index)
                return null;
            Character ch;
            if (((ch =cs[index]) == ' ' || ch == '\n')) {
                C t1c = statMapTranspose.get(nextC);
                if (t1c.isEnd) {
                    t.setEndIndex(index - 1);
                    return t1c;
                }
            }
        }
        return tc;
    }

    class C {
        String type = "";
        boolean isEnd;
        Set<Integer> si;
        C(Set<Integer> s) {
            si = s;
            isEnd = existsNntersection(si, nfaEndStat);
        }

        /**
         * 判断两个集合是否存在交集
         * @param s1
         * @param s2
         * @return
         */
        boolean existsNntersection(Set<Integer> s1, Set<Integer> s2) {
            if (s1.size() > s2.size())
                return existsNntersection(s2, s1);

            for (int i : s1)
                if (s2.contains(i)) {
                    if (null != typeMap && typeMap.containsKey(i))
                        type = typeMap.get(i);
                    return true;
                }

            return false;
        }

        @Override
        public String toString() {
//            if (null != type && type.length() != 0)
//                return type;
            return si.toString() + type;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            C c = (C) o;
            if (si.size() != c.si.size())
                return false;
            for (int i : si)
                if (!c.si.contains(i))
                    return false;
            return true;
        }

        @Override
        public int hashCode() {
            return si.size();
        }
    }

}
